package solutions;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: ws
 * Date: 2023-02-06
 * Time: 17:46
 */

//https://leetcode.cn/problems/permutation-in-string/submissions/399960694/?envType=study-plan&id=suan-fa-ru-men&plan=algorithms&plan_progress=bmyvagt

class Solution7 {
    //采用滑动窗口(大小逐渐变换)的思想
    public boolean checkInclusion(String s1, String s2) {
        int s1Len = s1.length();
        int s2Len = s2.length();
        if (s1Len > s2Len) {
            return false;
        }
        int[] cnt = new int[26];
        for (int i = 0; i < s1Len; ++i) {
            --cnt[s1.charAt(i) - 'a'];//统计各个字符出现的次数
        }
        int left = 0;//窗口的左边界
        for (int right = 0; right < s2Len; ++right) {//窗口的右边界
            int x = s2.charAt(right) - 'a';
            ++cnt[x];//匹配到一个加1，直到大于0
            while (cnt[x] > 0) {//大于零说明超出了s1的并查集，左边开始滑动
                --cnt[s2.charAt(left) - 'a'];//将该字符数减1
                ++left;//左边界滑动
            }
            if (right - left + 1 == s1Len) {
                return true;
            }
        }
        return false;
    }
}

//固定窗口滑动

//class Solution {
//    public boolean checkInclusion(String s1, String s2) {
//        int s1Len = s1.length();
//        int s2Len = s2.length();
//        if (s1Len > s2Len) {
//            return false;
//        }
//        int[] cnt1 = new int[26];
//        int[] cnt2 = new int[26];
//        for (int i = 0; i < s1Len; ++i) {//固定长度的窗口滑动
//            ++cnt1[s1.charAt(i) - 'a'];
//            ++cnt2[s2.charAt(i) - 'a'];
//        }
//        if (Arrays.equals(cnt1, cnt2)) {
//            return true;
//        }
//        for (int i = s1Len; i < s2Len; ++i) {//开始滑动窗口
//            ++cnt2[s2.charAt(i) - 'a'];//右边
//            --cnt2[s2.charAt(i - s1Len) - 'a'];//左边
//            if (Arrays.equals(cnt1, cnt2)) {
//                return true;
//            }
//        }
//        return false;
//    }
//}


class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int s1Len = s1.length();
        int s2Len = s2.length();
        if (s1Len > s2Len) {
            return false;
        }
        int[] cnt = new int[26];
        for (int i = 0; i < s1Len; ++i) {//固定长度的窗口滑动
            --cnt[s1.charAt(i) - 'a'];
            ++cnt[s2.charAt(i) - 'a'];
        }
        int diff = 0;
        for (int ele : cnt) {//关键思想
            if (ele != 0) {//统计出不同的字符种类数
                ++diff;
            }
        }
        if (diff == 0) {
            return true;
        }
        for (int i = s1Len; i < s2Len; ++i) {//开始滑动窗口
            int right = s2.charAt(i) - 'a';//右边
            int left = s2.charAt(i - s1Len) - 'a';//左边
            if (right == left) {//left和right等效替换
                continue;
            }
            if (cnt[right] == 0) {//如若之前没有right种类，则种类+1
                ++diff;
            }
            ++cnt[right];//记录改变
            if (cnt[right] == 0) {//right种类改变后抵消了，则right种类消失，种类-1
                --diff;
            }
            if (cnt[left] == 0) {//同理
                ++diff;
            }
            --cnt[left];
            if (cnt[left] == 0) {
                --diff;
            }
            if (diff == 0) {
                return true;
            }
        }
        return false;
    }
}